/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/first-position-of-target
   @Language: C++
   @Datetime: 16-02-09 04:47
   */

// Method 1
class Solution {
public:
	/**
	 * @param nums: The integer A.
	 * @param target: Target number to find.
	 * @return: The first position of target. Position starts from 0. 
	 */
	int binarySearch(vector<int> &A, int target) {
		// write your code here
		int begin=0, end=A.size(), mid=0;
		while(begin<end){
			mid = begin+(end-begin)/2;
			if (A[mid]>=target) end = mid;
			else begin = mid+1;
		}
		if (begin<A.size() && A[begin]==target) return begin;
		return -1;
	}
};

// Method 2, using stl algorithm
class Solution {
public:
	/**
	 * @param nums: The integer A.
	 * @param target: Target number to find.
	 * @return: The first position of target. Position starts from 0. 
	 */
	int binarySearch(vector<int> &A, int target) {
		// write your code here
		const auto &begin=lower_bound(A.begin(),A.end(),target);
		if (begin==A.end() || *begin!=target) return -1;
		return begin-A.begin();
	}
};
